1. Field of the Invention
This invention relates to switching systems and to methods of operation of switching systems. For example, the switching systems with which the invention is concerned might find application as crosspoint switches in local area network (LAN) switches, asynchronous transfer mode (ATM) switches and Internet protocol (IP) routers.
More particularly, the switching system to which the invention relates is intended for connection between a plurality of input lines and a plurality of output lines, and comprises a transfer stage operable to transfer packets of data from any of the input lines to those of the output lines for which those packets are destined. It is necessary with such switches to provide some form of queueing for the packets of data.
2. Description of the Prior Art
Many commercial switches and routers today employ output-queueing. When a packet arrives on an input line of an output queue switch, it is immediately transferred by the transfer stage to a queue at an output stage that is dedicated to its output line, where it will wait until departing from the switch. This approach is known to maximize the throughput of the switch; so long as no input or output is oversubscribed, the switch is able to support the traffic, and the occupancies of queues remain bounded.
The use of a separate queue for each output means that flows of packets for different outputs are kept separate, and cannot interfere with each other. By carefully scheduling the time a packet is placed onto the outgoing line, a switch or router can control the packet""s latency, and hence provide quality-of-service guarantees. But output queueing is impractical for switches with high line rates, or with a large number of ports. The fabric and memory (i.e. transfer stage) of an Nxc3x97N switch must run N times as fast as the line rate. Unfortunately, at high line rates, memories with sufficient bandwidth are simply not available.
On the other hand, the fabric and the memory of an input-queued switch need only run as fast as the line rate. This makes input queueing very appealing for switches with fast line rates, or with a large number of ports. For a given speed of memory, it is possible to build a faster switch; or for a given speed switch, it is possible to use slower, lower-cost memory device.
But, the main problem of input-queued switching is head-of-line blocking, whose effect on throughput can be severe. It has been shown that if each input maintains a single first-in-first-out queue, then head-of-line blocking can limit the throughput to just 58.6%.
One method that has been proposed to reduce head-of-line blocking is to increase the xe2x80x9cspeedupxe2x80x9d of a switch. A switch with a speedup of S can remove up to S packets from each input and deliver up to packets to each output within a time slot, where a time slot is the time between packet arrivals at the inputs. Hence, an output-queued switch has a speedup of S=N while an input-queued switch has a speedup of S=1. For values of S between 1 and N, buffers are needed at the inputs before switching as well as buffers at the outputs after switching. Hence such a switch will be referred to a combined-input-and-output-queued switch.
Both analytical and simulation studies of a combined-input-and-output-queued switch which maintains a single first-in-first-out queue at each input have been conducted for various values of the speedup. A common conclusion of these studies is that, with a speedup of S=4 or 5, one can achieve about 99% throughput when arrivals are independent and identically distributed at each input and the distribution of packet destinations is uniform across the outputs.
But it has been shown that a throughput of 100% can be achieved with a speedup of just one, if the inputs are arranged differently. That is, head-of-line blocking can be eliminated entirely using a scheme known as xe2x80x9cvirtual output queueingxe2x80x9d in which each input maintains a separate queue for each output. It has been shown that for independent arrivals, the throughput of an input-queued switch can be increased to 100%. The conclusion may be drawn that speedup is not necessary to eliminate the effect of head-of-line blocking.
In practice, it is not only the throughput of a switch which is of interest, but also the latency of individual packets. This is particularly important if a switch or router is to offer quality-of-service guarantees. Packets in an input-queued switch not only contend for an output, they also contend for entry into the switch fabric with packets that are destined for other outputs. This phenomenon is called xe2x80x9cinput contentionxe2x80x9d which places a packet at the mercy of other packets destined for other outputs. This is in stark contrast with an output-queued switch, where a packet is unaffected by packets destined for other outputs. The conclusion may be drawn that, to control delay, a mechanism is needed which eliminates input contention.
Previous studies of combined-input-and-output-queued switches make no guarantees about the delay of an individual packet, but only about average delay and throughput. The present invention is concerned with the delay of individual packets. Rather than find values of speedup that work well on average, or with simplistic traffic models, the invention is concerned with providing a combined-input-and-output-queued switch which behaves similarly, and preferably identically to an output-queued switch, preferably for all types of traffic, and preferably with the minimum speedup.
The present invention achieves this, in one aspect, by providing a method of operation of the switching system which comprises the steps of: for each output stage, noting the temporal order in which the packets destined for that output stage are received by the input stages; and controlling the transfer stage so that, for each output stage, the packets destined for that output stage are transferred from the input stages to that output stage in the noted order.
Preferably, the system operates according to time slots such that: no more than one packet is received by each input stage during each time slot; and no more than one packet is supplied by each output stage during each time slot; and each time slot is divided into a plurality of phases, for example between two and four such phases, such that: no more than one packet is transferred from each input stage by the transfer stage during each phase; and no more than one packet is transferred to each output stage by the transfer stage during each phase.
As will be shown later in this specification, if each such time slot is divided into four such phases (i.e. a speedup of four), the switching system can be made to behave identically to an output-queued switch.
In one example to achieve this, the controlling step includes the step, during each phase and for each output stage, of: selecting that one of the input stages, if any, having that one of the packets which are destined for that output stage which is earliest in the noted temporal order; and transferring that one packet from the selected input stage to that output stage unless there is input contention due to the selected input stage also having been selected for another of the output stages. If there is such input contention, that one of the output stages whose destined packet is earliest in the noted temporal order may be selected, unless there is none which is earliest. If none of the packets is earliest, selection between the output stages may be made in accordance with the predetermined ranking. In the case of input contention, the controlling step is preferably repeated for the or each output stage which is not selected in respect of the next earliest packet in the noted temporal order.
As in the known combined-input-and-output-queued switch, each input stage preferably comprises a plurality of input buffers, one for each output stage, the method further including the step of placing each received packet in that one of the input buffers for the input line on which that packet is received and for the output stage for which that packet is destined. Also, each output stage preferably comprises a respective output buffer for the packets, but, unlike the known output-queued switch or known combined-input-and-output-queued switch, the packets are preferably output from the respective output buffer to the respective output line in dependence upon the noted temporal order of the packets in the respective output buffer.
In accordance with another aspect of the invention, there is provided a switching system comprising: a plurality of output stages each operable to supply packets of data to a respective output line; a plurality of input stages each operable to receive packets of data on a respective input line, each received packet being destined for at least a respective one of the output stages; a transfer stage operable to transfer packets of data from any of the input stages to those of the output stages for which those packets are destined; means for detecting, for each output stage, the temporal order in which the packets destined for that output stage are received by the input stages; and means for controlling the transfer stage so that, for each output stage, the packets destined for that output stage are transferred from the input stages to that output stage in the detected temporal order.
Each output stage preferably comprises a respective output buffer for the packets, with the packets being supplied from that buffer to the respective output line in dependence upon the detected temporal order of the packets in the respective output buffer. Also, each input stage preferably comprises an input buffer for each output stage, such as a first-in-first-out buffer.
Other objects, features and advantages of the invention will be apparent from the following detailed description of the preferred embodiments of the invention, given purely by way of example.